package sort.insert;

import java.util.Arrays;

public class ShellSort {
	//设定排序距离量
	public int gap;

	public int temp;

	public int total;

	public int[] shellSort1(int[] array) {
		total = 0;
		//距离量控制
		for (gap = array.length/2; gap > 0; gap = gap/2) {
			//排序从分好的第一组开始,第一组下标0，gap
			for (int i = gap; i < array.length; i++) {
				//一次插入排序
				int j = i;
				temp = array[j];
				while(j-gap > 0) {
					//总数组下标间隔为gap
					if(array[j-gap] > temp) {
						array[j] = array[j-gap];
						j = j - gap;
					} else {
						break;
					}
				}
				total++;
				array[j] = temp;
			}
		}
		return array;
	}

	public static void main(String[] args) {
		ShellSort test = new ShellSort();
		int array[] = null;
		int array1[] = {1,9,8,8,8};
		int array2[] = {1,5,2,2,8,9,13,23,2,965};
		System.out.println("原数组：" + Arrays.toString(array1));
		System.out.println("原数组：" + Arrays.toString(array2));

		array = test.shellSort1(array1);
		System.out.println("SelectSort1：" + Arrays.toString(array));
		System.out.println("执行次数：" + test.total);

		array = test.shellSort1(array2);
		System.out.println("SelectSort1：" + Arrays.toString(array));
		System.out.println("执行次数：" + test.total);
	}

}
